﻿#include <iostream>
#include <stdexcept>
#include <vector>

using namespace std;
// 结构体定义-->描述单一个体
// 双向链表类似
struct TreeNode
{
	char data;
	struct TreeNode *left;
	struct TreeNode *right;
	TreeNode(char ch) : data(ch), left(nullptr), right(nullptr) {}
};
// 傻瓜式连接
// 创建节点：创建结构体变量
struct TreeNode *createNode(char data)
{
	struct TreeNode *newNode = (struct TreeNode *)malloc(sizeof(struct TreeNode));
	if (newNode == nullptr)
		return nullptr;
	newNode->data = data;
	newNode->left = nullptr;
	newNode->right = nullptr;
	return newNode;
}
// 插入节点
void insertNode(struct TreeNode *parent, struct TreeNode *left, struct TreeNode *right)
{
	parent->left = left;
	parent->right = right;
}

// 1 递归遍历
// a前序遍历
void preOrder(struct TreeNode *root)
{
	if (root)
	{
		printf("%c ", root->data);
		preOrder(root->left);
		preOrder(root->right);
	}
}

// b中序遍历
void middleOrder(struct TreeNode *root)
{
	if (root)
	{
		middleOrder(root->left);
		printf("%c ", root->data);
		middleOrder(root->right);
	}
}

// c后序遍历
void lastOrder(struct TreeNode *root)
{
	if (root)
	{
		lastOrder(root->left);
		lastOrder(root->right);
		printf("%c ", root->data);
	}
}

// 2 非递归遍历
// a栈（前序）
void stackPreOrder(struct TreeNode *root)
{
	if (root == nullptr)
	{
		throw std::underflow_error("Tree is empty");
	}

	struct TreeNode *stack[100];
	int nStackTop = -1;
	struct TreeNode *pMove = root;

	while (pMove != nullptr || nStackTop >= 0)
	{
		// 遍历左子树（路径最左节点）
		while (pMove != nullptr)
		{
			printf("%c ", pMove->data);
			stack[++nStackTop] = pMove;
			pMove = pMove->left;
		}

		// 处理栈顶元素（回溯）
		if (nStackTop >= 0)
		{
			pMove = stack[nStackTop--];
			pMove = pMove->right; // 转向右子树
		}
	}
}

// b栈（中序）
void stackMidOrder(struct TreeNode *root)
{
	if (root == nullptr)
	{
		throw std::underflow_error("Tree is empty");
	}
	struct TreeNode *pMove = root;
	struct TreeNode *stack[100];
	int nStackTop = -1;
	while (nStackTop >= 0 || pMove != nullptr)
	{
		while (pMove != nullptr)
		{
			stack[++nStackTop] = pMove;
			pMove = pMove->left;
		}
		if (nStackTop >= 0)
		{
			pMove = stack[nStackTop--];
			printf("%c ", pMove->data);
			pMove = pMove->right;
		}
	}
}
// c 栈（后序）
void stackLastOrder(struct TreeNode *root)
{
	if (root == nullptr)
	{
		throw std::underflow_error("Tree is empty");
	}
	struct TreeNode *pMove = root;
	struct TreeNode *stack[100];
	int nStackTop = -1;
	while (pMove)
	{
		stack[++nStackTop] = pMove;
		pMove = pMove->left;
	}

	struct TreeNode *lastVisit = nullptr; // 标记节点是否已经打印过了
	while (nStackTop >= 0)
	{
		pMove = stack[nStackTop--];
		// 如果没有右侧节点，并且没被打印，打印并标记已经打印
		if (pMove->right == nullptr || pMove->right == lastVisit)
		{
			printf("%c ", pMove->data);
			lastVisit = pMove;
		}
		// 如果有右侧节点，继续往右侧遍历
		else
		{
			stack[++nStackTop] = pMove;
			pMove = pMove->right;
			while (pMove)
			{
				stack[++nStackTop] = pMove;
				pMove = pMove->left;
			}
		}
	}
}

// 3 其他遍历
// 层次遍历-->广度遍历方式（BFS）
void layerOrder(struct TreeNode *root)
{
	if (root == nullptr)
	{
		throw std::underflow_error("Tree is empty");
	}
	struct TreeNode *pMove = root;
	struct TreeNode *queue[100];
	int nFront = 0; // 头
	int nTail = 0;	// 尾
	// 先入头节点
	queue[nTail++] = pMove;
	printf("%c ", pMove->data);
	while (nFront != nTail)
	{
		// 上个节点有左右值，入队并进行打印
		pMove = queue[nFront++];
		if (pMove->left)
		{
			queue[nTail++] = pMove->left;
			printf("%c ", pMove->left->data);
		}
		if (pMove->right)
		{
			queue[nTail++] = pMove->right;
			printf("%c ", pMove->right->data);
		}
	}
}

// 4 递归法创建
// ABD##E##C#FG###
void createTree(struct TreeNode **root)
{
	// char keyNode = 0;
	// scanf_s("%c", &keyNode, 1);
	
	char input[2];
    
    if (fgets(input, sizeof(input), stdin) == NULL) {
        *root = NULL;
        return;
    }
    
    // 清除可能的换行符
    input[strcspn(input, "\n")] = '\0';

	if (input[0] == '#')
	{
		*root = nullptr;
	}
	else 
	{
		*root = (struct TreeNode *)malloc(sizeof(struct TreeNode));
		if (*root == nullptr)
		{
			return;
		}
		(*root)->data = input[0];
		createTree(&(*root)->left);
		createTree(&(*root)->right);
	}
}

int main()
{
#if 0
	// 创建
	struct TreeNode *A = createNode('A');
	struct TreeNode *B = createNode('B');
	struct TreeNode *C = createNode('C');
	struct TreeNode *D = createNode('D');
	struct TreeNode *E = createNode('E');
	struct TreeNode *F = createNode('F');
	struct TreeNode *G = createNode('G');

	// 链接
	insertNode(A, B, C);
	insertNode(B, D, E);
	insertNode(C, nullptr, F);
	insertNode(F, G, nullptr);
#endif
	// 递归创建
	struct TreeNode *A = nullptr;
	createTree(&A);

	// 递归遍历
	printf("递归遍历：\n");
	printf("前序遍历：");
	preOrder(A);
	printf("\n栈 前序遍历：");
	stackPreOrder(A);
	printf("\n");

	printf("\n中序遍历：");
	middleOrder(A);
	printf("\n栈 中序遍历：");
	stackMidOrder(A);
	printf("\n");

	printf("\n后序遍历：");
	lastOrder(A);
	printf("\n栈 后序遍历：");
	stackLastOrder(A);
	printf("\n");

	printf("\n层次遍历：");
	layerOrder(A);
	printf("\n");

	return 0;
}